/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Wed Nov  4 13:45:05 2020
 * 
 * @brief  class Binary Tree
 * 
 * 
 */

#include <iostream>

template <typename T>
class Binary_Tree {
private:
    class Node {
    public:
	T data;
	Node* lc;
	Node * rc;
	Node * parent;
	int index; //the index of the node, to mark the order
        int t; //check if this node has been printed out.
    };
    Node * root;
    Node * min(Node * _x) const; //return the min node
    Node * max(Node * _x) const; //return the max node
    Node * successor(Node * _p) const; //return the node next to _p
    Node * predeccessor(Node * _p) const; //return the last noed
    Node * tree_search(T _x) const; //return the first node that its value equals _x
    void inorder_walk(Node * _x) const; //print the sub tree
public:
    Binary_Tree() { root = NULL; };
    Binary_Tree(T _data);
    void insert(T _data); //insert node
    void Delete(T _data); //delete node
    void print(); //print the tree
    void inorder_walk(); //print the tree
    T max(); //return the max
    T min(); //return the min
    void test_successor(T _x) const; //test the value next to _x
    void test_predeccessor(T _x) const; //test the last value of _x
    void search(T _x) const; //find the _x
    ~Binary_Tree();
};

template <typename T>
void Binary_Tree<T>::inorder_walk() {
    inorder_walk(root);
}

template <typename T>
void Binary_Tree<T>::inorder_walk(Node * _x) const {
    if (_x!=NULL) {
	//print the left
	inorder_walk(_x->lc);
	//print this node
	std::cout << "[" << _x->data << ", " << _x->index << "]" << std::endl;
	//print the right
	inorder_walk(_x->rc);
    }
}

template <typename T>
void Binary_Tree<T>::Delete(T _data) {
    //find the node
    Node * p = tree_search(_data);
    if (p==NULL) {
	return;
    }
    Node * q = p->parent;
    Node * lp = p->lc;
    Node * rp = p->rc;
    if (rp==NULL) {
	//if rp==NULL, just link the lp and p's parent, then delete p
	if (q!=NULL && q->lc==p) {
	    q->lc = lp;
	} else if (q!=NULL){
	    q->rc = lp;
	}
	if (lp!=NULL) {
	    lp->parent = q;
	}
	//if delete the root, change the root
	if (p==root) {
	    root = lp;
	}
	delete p;
    } else {
	//if has rp, choose the min of rp as the new node
        Node * new_n = min(rp);
	//if new node is not rp, link the new's parent and new's rc
	if (new_n!=rp) {	    
	    new_n->parent->lc = new_n->rc;
	    new_n->rc = rp;
	    if (rp!=NULL) {
		rp->parent = new_n;
	    }
	}
	//link the new and p's parent and p's lc
	new_n->parent = q;	
	new_n->lc = lp;
	if (lp!=NULL) {
	    lp->parent = new_n;
	}
	if (q!=NULL) {
	    if (q->lc==p) {
		q->lc = new_n;
	    } else {
		q->rc = new_n;
	    }
	}
	if (p==root) {
	    //if delete the root, change the root
	    root = new_n;
	}
	delete p;
    }
}

template <typename T>
void Binary_Tree<T>::search(T _x) const {
    Node * p = tree_search(_x);
    if (p!=NULL) {
	std::cout << "Find it!" << std::endl;
    } else {
	std::cout << "Not Found!" << std::endl;
    }
}

template <typename T>
void Binary_Tree<T>::test_predeccessor(T _x) const {
    Node * p = tree_search(_x);
     if (p==NULL) {
	std::cout << "Not Found!" << std::endl;
	return;
    }   
    Node * q = predeccessor(p);
    if (q==NULL) {
	std::cout << "Not Found!" << std::endl;
	return;
    }
    std::cout << "This is the last: "<< q->data << std::endl;
}

template <typename T>
void Binary_Tree<T>::test_successor(T _x) const {
    Node * p = tree_search(_x);
    if (p==NULL) {
	std::cout << "Not Found!" << std::endl;
	return;
    }
    Node * q = successor(p);
    if (q==NULL) {
	std::cout << "Not Found!" << std::endl;
	return;
    }
    std::cout << "This is the next: "<< q->data << std::endl;
}

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::tree_search(T _x) const{
    Node * index = root;
    while (index!=NULL) {
	if (_x<index->data) {
	    index = index->lc;
	} else if (_x==index->data){
	    return index;
	} else {
	    index = index->rc;
	}
    }
    return NULL;
}

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::predeccessor(Node * _p) const {
    Node * index = _p;
    //if has left, return the max of left
    if (index->lc!=NULL) {
	return max(index->lc);
    }
    Node * last = index;
    index = index->parent;
    //if no left, find parent until index==NULL or index come from right
    while (index!=NULL && index->lc==last) {
        last = index;
	index = index->parent;
    }
    return index;
}

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::successor(Node * _p) const {
    Node * index = _p;
    //if has right, return the min of right
    if (index->rc!=NULL) {
	return min(index->rc);
    }
    Node * last = index;
    index = index->parent;
    //if no right, find parent until index==NULL or index come from left
    while (index!=NULL && index->rc==last) {
	last = index;
	index = index->parent;
    }
    return index;
}

template <typename T>
T Binary_Tree<T>::min() {
    Node * p = min(root);
    
    if (p!=NULL) {
	return p->data;
    }
    return 0;
}

template <typename T>
T Binary_Tree<T>::max() {
    Node * p = max(root);
    
    if (p!=NULL) {
	return p->data;
    }
    return 0;
}

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::max(Node * _x) const {
    Node * index = _x;
    //return the most right node, it is the max
    while (index->rc!=NULL) {
	index = index->rc;
    }

    return index;
}

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::min(Node * _x) const {
    Node * index = _x;
    //return the most left node, it is the min
    while (index->lc!=NULL) {
	index = index->lc;
    }
    
    return index;
}

template <typename T>
Binary_Tree<T>::~Binary_Tree() {
    Node * index = root;
    Node * last = index;

    if (root!=NULL) {
	while (1) {
	    //move the index to the left until null
	    while (index->lc!=NULL) {
		last = index;
		index = index->lc;
	    }

	    //if no node at right, delete it
	    if (index->rc==NULL) {
	        delete index;
		last->lc = NULL;
		last->rc = NULL;
	        index = last;
		//if it is the root, delete it and end
		if (index==root) {
		    delete index;
		    break;
		}
		last = index->parent;
	    } else {
		//if there are right nodes, move to the right
		last = index;
		index = index->rc;
	    }
	}
    }
}

template <typename T>
void Binary_Tree<T>::print() {
    Node * index = root;
    std::cout << "Tree = [";

    //if empty, do nothing
    if (index==NULL) {
	return;
    } else {
	while (1) {
	    //move to the left if there are left children and have not been printed out
	    while (index->lc!=NULL && index->lc->t==0) {
		index = index->lc;
	    }
	    //if has not been printed out, print out
	    if (index->t==0) {
		std::cout << index->data << ", ";
		index->t = 1;
	    } else {
		//if has been printed out, move to the parent
		index = index->parent;
		//if parent has not been printed out, print out
		if (index->t==0) {
		    std::cout << index->data << ", ";
		    index->t = 1;		    
		}
		//if this is the root, end
		if (index==root && index->t==1) {
		    break;
		}
	    }
	    //if there are right children and not been printed out, move to the right
	    if (index->rc!=NULL && index->rc->t==0) {
		index = index->rc;
	    }
	}
	std::cout << "\b\b]" << std::endl;
    }
}

template <typename T>
void Binary_Tree<T>::insert(T _data) {
    //insert the node to the NULL node
    Node * index = root;
    Node * p = new Node;
    p->data = _data;
    p->t = 0;
    p->index = 0;
    
    if (root==NULL) {
	p->lc = p->rc = NULL;
	p->parent = NULL;
        root = p;
    } else {
        while (1) {
	    if (_data<index->data) {
		if (index->lc==NULL) {
		    index->lc = p;
		    p->lc = p->rc = NULL;
		    p->parent = index;
		    break;		    
		} else {
		    index = index->lc;
		}
	    } else {
		if (_data==index->data) {
		    p->index += 1;
		}
		if (index->rc!=NULL) {
		    index = index->rc;
		} else {
		    index->rc = p;
		    p->lc = p->rc = NULL;
		    p->parent = index;
		    break;
		}
	    }
	}	
    }
}

template <typename T>
Binary_Tree<T>::Binary_Tree(T _data) {
    root = new Node;
    root->data = _data;
    root->lc = root->rc = root->parent = NULL;
    root->t = 0;
    root->index = 0;
}
